Mission Scheduling (MS) is a problem that arises in the management of networks of heterogeneous resources, such as sensor and satellite networks. In this context, a mission is a collection of tasks that can each be executed by some subset of the resources.
Various commercial off-the-shelf (COTS) products are available as prior art for scheduling problems. Such products include manufacturing and integer programming (IP) products. However, these have no proven history with MS-sized problems and major modifications may be needed to address MS. In addition, COTS adds risk-of-lifecycle costs. Prior algorithms such as greedy (task-based algorithms) and meta-heuristics approaches have been developed for scheduling problems. Again, these have mostly been applied to smaller-sized problems and significant modifications may be needed to make them scale to larger problems and still be able to provide near-optimal solutions. Additionally, the non-COTS approaches do not generally have built-in time-budgeting mechanisms.
As briefly described above, one aspect of scheduling is related to manufacturing problems and supply chain management. Commercial products are available from Manugistics Inc., Ariba, and i2 Technologies Inc., though these tools tend to be specifically tailored to the demands of manufacturing industries. Major modifications would be necessary to apply the techniques used in these products to MS and even then, these tools would not necessarily work on problems with the scale of MS. Manugistics Inc. is located at 9715 Key West Avenue, Rockville, Md. 20850. Ariba is located at 807 11th Avenue, Sunnyvale, Calif. 94089. Additionally, i2 Technologies Inc. is located at One i2 Place, 11701 Luna Road, Dallas, Tex. 75234.
Integer programming (IP) is the method typically used for finding optimal solutions to all sorts of difficult scheduling problems. High-quality, commercially-available solvers (such as ILOG's OPL/CPLEX software, Dash Optimization's Xpress-MP software, and Optimal Solution Technologies' IBM/OSL software) make IP a desirable framework for solving scheduling problems. ILOG Inc. is located at 1080 Linda Vista Avenue, Mountain View, Calif. 94043. Dash Optimization Inc. is located at 560 Sylvan Avenue, Englewood Cliffs, N.J. 07632. Optimal Solution Technologies Inc. is located at P.O. Box 201964, Shaker Heights, Ohio 44120-1964. The problem with these solvers is that large-sized problems cannot be solved in a reasonable amount of time. Most IP solvers rely on branch-and-bound or similar techniques which can include an exponential number of variables. An instance of MS will often have millions of variables, making IP, as well as any optimal approach, infeasible. As described in further detail below, Billups et al. conducted a thorough investigation of using IP techniques to solve a simpler version of MS. The study confirmed that none but the simplest of problems can be solved optimally using IP.
Optimal techniques for scheduling problems (e.g., branch-and-bound) can have an exponential running time in the number of available timeslots for scheduling tasks. Some instances of the MS problem can include millions of timeslots. Thus, finding optimal solutions is completely infeasible. As can be appreciated by one skilled in the art, the scale of MS problems is large, even for suboptimal solution techniques. Though little work has been done on MS itself, algorithms for solving related problems have been limited to a much smaller scale. For example, a problem having 2500 timeslots was described by E. Johnson and A. Antunes, in an article entitled, “A high capacity object oriented mission scheduling system for XTE,” in Astronomical Data Analysis Software and Systems V, pp. 463-466, 1996.
Other systems have attempted scheduling using greedy and genetic algorithm (GA)-based approaches. However, they have been limited to simpler versions of MS. For example, Billups et al. developed several GA algorithms for a satellite scheduling problem that is similar to MS. However, it only included a single resource (which makes IP methods much more tractable) and allowed for less freedom in how the different tasks of a single mission can be scheduled. The developments by Billups et al. were described in a publication entitled, “Satellite payload scheduling with dynamic tasking,” in Mathematics Clinic, Univ. of Colorado, Denver, found at http://www.math.cudenver.edu/clinic/reports/ClinicReportSpring2005.pdf.gz, Spring 2005.
Similarly, Becker and Smith developed an incremental approach to a problem that looks similar to MS but is extremely domain-dependant. Therefore, their positive results do not generally translate to MS. The Becker and Smith approach was described in a publication entitled, “Mixed initiative resource management: The AMC Barrel Allocator,” in Proceedings of the Fifth International Conference on AI Planning and Scheduling, pp. 32-41, Breckenridge, Co., April 2000.
Because of the inherent difficulty and large size of most real-world scheduling problems, most research has focused on suboptimal, meta-heuristic algorithms. Rabideau et al. and Dorn et al. discuss techniques for solving difficult scheduling problems through the processes of iterative improvement and repair. Rabideau et al. is a publication authored by G. Rabideau, S. Chien, J. Willis, and T. Mann, entitled, “Using iterative repair to automate planning and scheduling of shuttle payload operations,” in Innovative Applications of Artificial Intelligence (IAAI), Orlando, Fla., July 1999. Additionally, Dorn et al. is a publication authored by J. Dorn, M. Girsch, G. Skele, and W. Slany, entitled, “Comparison of iterative improvement techniques for schedule optimization,” in European Journal of Operations Research, 94(2), pp. 349-61, 1996. Such techniques recognize that solutions can be found quickly by building them in an iterative fashion. While the techniques described above provide a fundamental foundation for applying techniques like Genetic Algorithms (GA) and Tabu Search to automatic scheduling problems, much of their gains are lost when applying them to a problem like MS. Such techniques were not explicitly designed to solve an MS problem. This is a common problem in applying prior art in scheduling domains, as performance is degraded when general methods are applied to specific problems and domain-dependant advances do not often translate to even slightly different problems.
A lot of prior work has been completed using GAs for scheduling problems. By way of example, Shi et al. describes a GA approach to Job Shop Scheduling problems, while Ozdamar, Dorn et al., and Shtub et al. propose GA approaches to more general scheduling problems. Shi et al. is a publication authored by G. Shi, H. lima, and N. Sannomiya, entitled, “A new encoding scheme for solving job shop problems by genetic algorithm,” in Proceedings of the 35th Conference on Decision and Control, Kobe, Japan, December 1996. Ozdamar is a publication authored by L. Ozdamar, entitled, “A genetic algorithm approach to a general category project scheduling problem,” in IEEE Transactions on Systems, Man, and Cybernetics—Part C: Applications and Reviews, 29(1), February 1999. Shtub et al. is a publication authored by A. Shtub, L. J. LeBlanc, and Z. Cai, entitled, “Scheduling programs with repetitive projects: A comparison of a simulated annealing, a genetic and a pair-wise swap algorithm,” in European Journal of Operations Research, 88, pp. 124-38, 1996.
Though using GAs is a promising technique, its incarnations in prior work have limited applicability to MS because of fundamental differences in the objective functions and constraints for which they were developed. There has also been work on scheduling with evolution programs (i.e., Cheng and Gen, and Mesghouni et al.), though such work suffers from the same limitations as GA when applied to MS. Cheng and Gen is a publication authored by R. Cheng and M. Gen, entitled, “Evolution program for resource constrained project scheduling problem,” in Proceedings of the First IEEE Conference on Evolutionary Computational Intelligence, 2, pp. 736-41, 1994. Additionally, Mesghouni et al. is a publication authored by K. Mesghouni, S. Hammadi, and P. Borne, entitled, “Evolution programs for job-shop scheduling,” in IEEE Transactions on Systems, Man, and Cybernetics, pp. 720-25, 1997.
Simulated Annealing (SA) is a technique used by the present invention that also appears throughout the literature. For example, Yamada et al. describes tailoring SA to Job Shop Scheduling, while Hindsberger et al. describes its application to Target-Radar allocation. Yamada et al. is a publication authored by T. Yamada, B. E. Rosen, and R. Nakano, entitled, “A simulated annealing approach to job shop scheduling using critical block transition operators,” in Proceedings of the IEEE International Conference on Neural Networks (ICNN), pp. 4687-92, 1994. Hindsberger et al. is a publication authored by M. Hindsberger and R. V. V. Vidal, entitled, “Tabu search for target-radar allocation,” in Technical Report, IMM Publications, which can be found at http://www2.imm.dtu.dk/pubdb/views/edoc_download.php/506/pdf/imm506.pdf, 1998.
Job Shop Scheduling is a fundamentally different scheduling problem than MS. Methods for solving Job Shop Scheduling do not necessarily work well for MS, and vice versa. Hindsberger and Vidal concluded that a Tabu Search algorithm worked better than SA for their particular problem because of the limited amount of “cooling time” they could afford to give their SA algorithm.
One of the problems with relying on prior work for MS solvers is the difficulty with preserving solution quality when translating the intended scheduling problem to MS. A possible way of resolving this is to focus on a simpler version of MS that includes only missions with a single task. This task-based scheduling has much more in common with more general scheduling problems and should therefore have more success in utilizing existing solution techniques. However, research has indicated that while task-based techniques are easy to implement and often more intuitive, the solutions are often very low quality. Thus, techniques tailored for MS far out perform the simpler task-based techniques.
The prior art mentioned above is limited and incomplete because it cannot solve MS-sized problems with the desired optimization objectives. Thus, a continuing need exists for a system that addresses the need of solving MS-sized problems, yet still provides a high quality solution.